<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 返回矩阵中非1的元素个数（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>存在一个m*n的二维数组&#xff0c;其成员取值范围为0&#xff0c;1&#xff0c;2。</p> 
<p>其中值为1的元素具备同化特性&#xff0c;每经过1S&#xff0c;将上下左右值为0的元素同化为1。</p> 
<p>而值为2的元素&#xff0c;免疫同化。</p> 
<p>将数组所有成员随机初始化为0或2&#xff0c;再将矩阵的[0, 0]元素修改成1&#xff0c;在经过足够长的时间后求矩阵中有多少个元素是0或2&#xff08;即0和2数量之和&#xff09;。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入的前两个数字是矩阵大小。后面是数字矩阵内容。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>返回矩阵中非1的元素个数。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4 4<br /> 0 0 0 0<br /> 0 2 2 2<br /> 0 2 0 0<br /> 0 2 0 0</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">9</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>输入数字前两个数字是矩阵大小。后面的数字是矩阵内容。</p> <p>起始位置(0,0)被修改为1后&#xff0c;最终只能同化矩阵为&#xff1a;</p> <p>1 1 1 1</p> <p>1 2 2 2</p> <p>1 2 0 0</p> <p>1 2 0 0</p> <p>所以矩阵中非1的元素个数为9</p> </td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以使用广度优先搜索BFS解决。</p> 
<p>关于广度优先搜索&#xff0c;可以看&#xff1a;<a href="https://blog.csdn.net/qfc_128220/article/details/127711317?ops_request_misc&#61;&amp;request_id&#61;e141160e21514bfeb944cf26bc3c5031&amp;biz_id&#61;&amp;utm_medium&#61;distribute.pc_search_result.none-task-blog-2~blog~koosearch~default-1-127711317-null-null.268%5Ev1%5Econtrol&amp;utm_term&#61;%E8%AE%A1%E7%AE%97%E7%96%AB%E6%83%85&amp;spm&#61;1018.2226.3001.4450" title="华为OD机试 - 计算疫情扩散时间&#xff08;Java &amp; JS &amp; Python&#xff09;_在一个地图中(地图由n*n个区域组成)_伏城之外的博客-CSDN博客">华为OD机试 - 计算疫情扩散时间&#xff08;Java &amp; JS &amp; Python&#xff09;_在一个地图中(地图由n*n个区域组成)_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let m, n;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61; 1) {
    [m, n] &#61; lines[0].split(&#34; &#34;).map(Number);
  }

  if (m &amp;&amp; lines.length &#61;&#61; m &#43; 1) {
    lines.shift();

    const matrix &#61; lines.map((s) &#61;&gt; s.split(&#34; &#34;).map(Number));
    matrix[0][0] &#61; 1;

    console.log(getResult(m, n, matrix));
  }
});

function getResult(m, n, matrix) {
  // 上、下、左、右偏移量
  const offsets &#61; [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  // 广搜队列, 初始时只有矩阵[0,0]位置元素为1
  const queue &#61; [[0, 0]];

  // count记录矩阵中值为1的元素的个数
  let count &#61; 1;

  // 广搜
  while (queue.length &gt; 0) {
    const [x, y] &#61; queue.shift();

    for (let offset of offsets) {
      const newX &#61; x &#43; offset[0];
      const newY &#61; y &#43; offset[1];

      if (
        newX &gt;&#61; 0 &amp;&amp;
        newX &lt; m &amp;&amp;
        newY &gt;&#61; 0 &amp;&amp;
        newY &lt; n &amp;&amp;
        matrix[newX][newY] &#61;&#61; 0
      ) {
        matrix[newX][newY] &#61; 1;
        count&#43;&#43;;
        queue.push([newX, newY]);
      }
    }
  }

  return m * n - count;
}
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; sc.nextInt();
    int n &#61; sc.nextInt();

    int[][] matrix &#61; new int[m][n];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        matrix[i][j] &#61; sc.nextInt();
      }
    }

    matrix[0][0] &#61; 1;

    System.out.println(getResult(m, n, matrix));
  }

  public static int getResult(int m, int n, int[][] matrix) {
    // 上、下、左、右偏移量
    int[][] offsets &#61; {<!-- -->{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 广搜队列
    LinkedList&lt;int[]&gt; queue &#61; new LinkedList&lt;&gt;();

    // 初始时只有矩阵[0,0]位置元素为1
    queue.add(new int[] {0, 0});

    // count记录矩阵中值为1的元素的个数
    int count &#61; 1;

    // 广搜
    while (queue.size() &gt; 0) {
      int[] pos &#61; queue.removeFirst();

      int x &#61; pos[0];
      int y &#61; pos[1];

      for (int[] offset : offsets) {
        int newX &#61; x &#43; offset[0];
        int newY &#61; y &#43; offset[1];

        if (newX &gt;&#61; 0 &amp;&amp; newX &lt; m &amp;&amp; newY &gt;&#61; 0 &amp;&amp; newY &lt; n &amp;&amp; matrix[newX][newY] &#61;&#61; 0) {
          matrix[newX][newY] &#61; 1;
          count&#43;&#43;;
          queue.add(new int[] {newX, newY});
        }
      }
    }

    return m * n - count;
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
m, n &#61; map(int, input().split())
matrix &#61; [list(map(int, input().split())) for _ in range(m)]
matrix[0][0] &#61; 1


# 算法入口
def getResult():
    # 上、下、左、右偏移量
    offsets &#61; ((-1, 0), (1, 0), (0, -1), (0, 1))

    # 广搜队列, 初始时只有矩阵[0,0]位置元素为1
    queue &#61; [[0, 0]]

    # count记录矩阵中值为1的元素的个数
    count &#61; 1

    # 广搜
    while len(queue) &gt; 0:
        x, y &#61; queue.pop(0)

        for offset in offsets:
            newX &#61; x &#43; offset[0]
            newY &#61; y &#43; offset[1]

            if m &gt; newX &gt;&#61; 0 and n &gt; newY &gt;&#61; 0 and matrix[newX][newY] &#61;&#61; 0:
                matrix[newX][newY] &#61; 1
                count &#43;&#61; 1
                queue.append([newX, newY])

    return m * n - count


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

/**
 * 下面时基于单向链表实现的队列&#xff0c;入队enqueue&#xff0c;出队dequeue
 */
typedef int bool;
#define TRUE 1
#define FALSE 0

// 队列元素类型&#xff08;初始默认为int&#xff0c;后期可以改为需要的类型&#xff09;
typedef int E;

// 单向链表节点结构体
typedef struct ListNode {
    E ele; // 节点值
    struct ListNode *next; // 后继节点
} Node;

// 链表结构体
typedef struct LinkedList {
    Node *head; // 头节点
    Node *tail; // 尾节点
    int size; // 队列长度
} Queue; // 使用链表模拟队列

/*!
 * 初始化队列
 * &#64;return 队列指针
 */
Queue *init() {
    // 申请内存
    Queue *queue &#61; (Queue *) malloc(sizeof(Queue));

    // 申请内存失败
    if (queue &#61;&#61; NULL) {
        return NULL;
    }

    // 初始化队列成员
    queue-&gt;head &#61; NULL;
    queue-&gt;tail &#61; NULL;
    queue-&gt;size &#61; 0;

    return queue;
}

/*!
 * 释放队列
 * &#64;param queue 队列
 */
void destroy(Queue* queue) {
    Node* cur &#61; queue-&gt;head;

    // 释放队列各个节点的内存
    while(cur !&#61; NULL) {
        Node* tmp &#61; cur-&gt;next;
        free(cur);
        cur &#61; tmp;
    }

    // 释放队列结构体内存
    free(queue);
}

/*!
 * 入队
 * &#64;param queue 队列
 * &#64;param ele 入队元素
 * &#64;return 操作结果
 */
bool enqueue(Queue* queue, E ele) {
    // 申请内存&#xff0c;创建一个新节点
    Node *node &#61; (Node *) malloc(sizeof(Node));

    // 申请内存失败
    if (node &#61;&#61; NULL) {
        return FALSE;
    }

    // 初始化节点
    node-&gt;ele &#61; ele;
    node-&gt;next &#61; NULL;

    if (queue-&gt;size &#61;&#61; 0) {
        // 空队列插入
        queue-&gt;head &#61; node;
        queue-&gt;tail &#61; node;
    } else {
        // 尾插
        queue-&gt;tail-&gt;next &#61; node;
        queue-&gt;tail &#61; node;
    }

    // 节点数&#43;1
    queue-&gt;size&#43;&#43;;

    return TRUE;
}

/*!
 * 出队
 * &#64;param queue 队列
 * &#64;return 出队元素的地址&#xff08;注意&#xff1a;返回值特地申请了一块内存来存储&#xff0c;因此使用完后&#xff0c;需要释放返回值占用的内存&#xff09;
 */
E* dequeue(Queue* queue) {
    // 空队列无法出队
    if(queue-&gt;size &#61;&#61; 0) {
        return NULL;
    }

    // 指向将被删除节点
    Node *removeNode;

    if (queue-&gt;size &#61;&#61; 1) {
        // 单节点队列删除唯一节点
        removeNode &#61; queue-&gt;head;
        queue-&gt;head &#61; NULL;
        queue-&gt;tail &#61; NULL;
    } else {
        // 头删
        removeNode &#61; queue-&gt;head;
        queue-&gt;head &#61; queue-&gt;head-&gt;next;
    }

    // 队列节点个数-1
    queue-&gt;size--;

    // 申请一块内存用于存放被删除节点的值
    E *p &#61; (E *) malloc(sizeof(E));
    *p &#61; removeNode-&gt;ele;

    // 释放被删除节点的空间
    free(removeNode);

    return p;
}


/**
 * 算法代码逻辑
 */

#define MAX_ROWS 100
#define MAX_COLS 100

int m, n;
int matrix[MAX_ROWS][MAX_COLS];

int getResult();

int main() {
    scanf(&#34;%d %d&#34;, &amp;m, &amp;n);

    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
        for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
            scanf(&#34;%d&#34;, &amp;matrix[i][j]);
        }
    }

    matrix[0][0] &#61; 1;

    printf(&#34;%d\n&#34;, getResult());

    return 0;
}

int getResult() {
    int offsets[4][2] &#61; {<!-- -->{-1, 0},
                         {1,  0},
                         {0,  1},
                         {0,  -1}};

    Queue *queue &#61; init();

    enqueue(queue, 0 * n &#43; 0);
    int count &#61; 1;

    while (queue-&gt;size &gt; 0) {
        int* pos &#61; dequeue(queue);

        int x &#61; *pos / n;
        int y &#61; *pos % n;

        // dequeue返回值是存放在一块专门申请的内存中的&#xff0c;因此需要释放
        free(pos);

        for (int i &#61; 0; i &lt; 4; i&#43;&#43;) {
            int newX &#61; x &#43; offsets[i][0];
            int newY &#61; y &#43; offsets[i][1];

            if (newX &gt;&#61; 0 &amp;&amp; newX &lt; m &amp;&amp; newY &gt;&#61; 0 &amp;&amp; newY &lt; n &amp;&amp; matrix[newX][newY] &#61;&#61; 0) {
                matrix[newX][newY] &#61; 1;
                count&#43;&#43;;
                enqueue(queue, newX * n &#43; newY);
            }
        }
    }

    // 释放链表内存
    destroy(queue);

    return m * n - count;
}</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>